from typing import List


class Solution:
    def __init__(self):
        self.temp = {}

    def maxCoins(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        tp = tuple(nums)
        if tp not in self.temp:
            li = []
            for i in range(len(nums)):
                if i == 0:
                    li.append(nums[0] * nums[1] + self.maxCoins(nums[1:]))
                elif i == len(nums) - 1:
                    li.append(nums[i - 1] * nums[i] + self.maxCoins(nums[:-1]))
                else:
                    li.append(nums[i - 1] * nums[i] * nums[i + 1] + self.maxCoins(nums[:i] + nums[i+1:]))
            self.temp[tp] = max(li)
        return self.temp[tp]

# print(Solution().maxCoins([3,1,5,8]))
# print(Solution().maxCoins([9,76,64,21,97,60,5])) # 卧槽，怎么排查？
# print(Solution().maxCoins([7,9,8,0,7,1,3,5,5,2,3]))

solu = Solution()
x = solu.maxCoins([8,3,4,3,5,0,5,6,6,2,8,5,6,2,3,8,3,5,1,0,2])
print(x)



